package test;
/*
题目 53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
数据
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 */
public class leetcode53_zuidazixuliehe {
    //暴力法   复杂度为o(n*n)
    public static  int maxSubArray(int nums[]){
        if(nums.length==0) return 0;
        int m= Integer.MIN_VALUE,sum=0;
        for(int i=0;i<nums.length;i++){
            sum=0;
            for(int j=i;j<nums.length;j++){
                sum=sum+nums[j];
                m=Math.max(sum,m);
            }
        }
        return m;
    }
   //分治法  分为两个部分  复杂度为o(n)
   public static int maxSubArray1(int nums[],int begin,int end){
       if(nums.length==0) return 0;
       if(end-begin<2) return nums[begin];   //只有一个元素
       int mid=(end+begin)>>1;
       int leftmax=Integer.MIN_VALUE,rightmax=Integer.MIN_VALUE,leftsum=0,rightsum=0;   //从中心节点向两边计算出最大
       for(int i=mid-1;i>=begin;i--){
           leftsum+=nums[i];
           leftmax=Math.max(leftmax,leftsum);

       }
       for(int i=mid;i<end;i++){
           rightsum+=nums[i];
           rightmax=Math.max(rightmax,rightsum);
       }
       int max=leftmax+rightmax;
       return Math.max(Math.max(maxSubArray1(nums,begin,mid),maxSubArray1(nums,mid,end)),max);               //选出左边最大和右边最大的或者中间最大
   }
    public static void main(String[] args) {
        int nums[]={-2,1,-3,4,-1,2,1,-5,4};
       // System.out.println( maxSubArray(nums));
        System.out.println(maxSubArray1(nums,0,nums.length));
    }
}
